1. Field of the Invention
Embodiments herein present a method, system, computer program product, etc. for self-modulation in the selection and execution of corrective actions in a model-based automated management framework.
2. Description of the Related Art
Within this application several publications are referenced by arabic numerals within brackets. Full citations for these publications may be found at the end of the specification immediately preceding the claims. The disclosures of all these publications in their entireties are hereby expressly incorporated by reference into the present application for the purposes of indicating the background of the present invention and illustrating the state of the art.
There are several techniques for automated system management—the existing taxonomy consists of rule-based, feedback-based, and model-based approaches. Each of these techniques has its advantages and disadvantages (as described below). The models used for predicting behavior are not always accurate, leading to selection and execution of incorrect actions, eventually leading to undesirable system behavior.
The popular approaches for system management are rule-based. These approaches have not become popular for real-world management scenarios, primarily because of the complexity involved in writing rules and the brittleness of the rules with respect to the underlying physical configuration. The alternatives to rule-based system management can be categorized into: Feedback-based systems and Model-based systems. Feedback-based systems rely on iteratively adjusting the values by observing the state of the system; provided that a tuning problem is amenable to the use of feedback and that the optimal knob settings can be reached in a reasonable amount of time, feedback-based tuning methods have the advantage of being able to adapt easily to changes in the environment. Further, such methods are able to perform well without any training (and thus can handle previously unseen workloads). On the other hand, Model-based systems create predictions for the behavior of the system for different workload characteristics, and configuration parameters; they can be used to distinguish between the global optimal state from the local optimas. But both feedback-based and model-based have limitations that have limited their use in real-world system management applications. These limitations are enumerated as follows:
For feedback-systems, it is often difficult to use feedback to tune multiple knobs simultaneously. With a single knob, the tuner only needs to decide whether to increase or decrease the current knob setting, whereas adjustments to multiple knobs require an understanding of how the knobs interact and how they jointly affect the performance of the system. Moreover, a large number of knob adjustments may be needed before the optimal knob settings are reached, and this may lead to unreasonable runtime costs for the tuner (which may not also be feasible in real systems). Further, it is difficult to apply feedback mechanisms to tuning problems whose performance metrics do not have obvious critical values. For example, if attempting to maximize the throughput of a database system, the critical (i.e., maximal) throughput value is not known ahead of time, and the impact of the knobs on throughput may be complicated. Finally, some knobs may be expensive enough to adjust that it would be impractical to iteratively adjust them in a search for the optimal settings, even if only a small number of adjustments are needed.
For model-based systems, they typically require an initial expenditure of time to train the model; in such cases, the model's predictions are not accurate until sufficient training data has been collected. In addition, it can be difficult to devise an accurate performance model for a complex software system. As the number of variables relevant to the tuning problem increases and, in particular, as tuning of an increasing number of interacting knobs is attempted, the challenge of developing an accurate model also increases.
In regards to feedback systems, Weikum et al. use a feedback-driven approach to tune a database systems multiprogramming level (MPL), a knob that limits the number of concurrent accesses to the database. They base the adjustments to this knob on a measure of lock contention in the system: when this metric exceeds a critical value, the MPL is reduced, and when it drops below the critical value, the MPL is increased. The authors determined the critical value experimentally, and they claim that it does not need to be fine-tuned; rather, they present the results of experiments demonstrating that there is a range of critical values that perform well on a wide range of workloads. The authors also present results showing that their approach allows the system to provide acceptable response times under extremely high loads.
Kurt Brown et al. use mechanisms based on feedback to tune knobs related to memory management and load control in a database system. The objective of the tuning is to meet the response-time goals of individual workload classes in a multiclass database workload, and the knobs are adjusted until either these goals are met or until the tuner determines that they cannot be met. The workload classes are tuned separately, and heuristics are used to address interdependencies between classes. Depending on the nature of a given class's memory usage, either one or two knobs are adjusted, and estimates and heuristics are used to guide the adjustments. Simulations used to validate the author's proposed mechanisms show that both the one-knob and two-knob timers are able to meet the goals of a variety of workloads, although the authors acknowledge that it can take a long time to achieve the response-time goals of certain types of workloads. The model-based approach presented, on the other hand, is able to avoid the potentially lengthy series of iterative adjustments that a feedback-based approach may require.
Microsoft's SQL Server employs feedback-based tuning to adjust the size of its cache of database pages. The adjustments are based on the amount of free physical memory in the system: when the number of free memory pages drops below one threshold, the size of the database cache is reduced; when the number of free pages exceed a second threshold, the cache size is increased. The authors of the paper that mentions this use of feedback-based tuning do not explain how the threshold values are chosen. The authors also outline plans to use feedback to adjust the number of pages read into the cache when the system performs read-ahead (i.e., when it proactively reads in pages that it anticipates will be accessed soon).
In the SEDA framework for highly concurrent Internet applications, applications consist of a series of components called stages that are connected by queues of events, and feedback-driven tuners called resource controllers are used to dynamically adjust each stage's resource usage. For example, a stage's thread pool controller tunes the number of threads associated with the stage, adding a thread when the length of the stage queue rises above some threshold and removing a thread when it sits idle for longer than a second threshold, SEDA's resource controllers operate at the application level, without needing to he aware of the resource management policies of the underlying operating system. It is unclear how sensitive these controllers are to the thresholds used to guide the knob adjustments, but the authors present results that demonstrate the ability of the resource controllers to effectively adapt to increasing load.
Feedback mechanisms have also been widely applied to resource management problems in operating systems, including CPU scheduling and network congestion and how control. To facilitate the use of feedback-based tuners in this domain, Goel et al. have developed a toolkit of simple, modular feedback components that can be combined and reused. However, all of their example tuners adjust a single knob, and it is unclear whether their components can effectively handle software-tuning problems that involve the simultaneous adjustment of multiple knobs.
More generally, almost all of the examples presented in this section involve tuning individual knobs in isolation. The one exception is the work of Brown et al., who tone two knobs simultaneously for one class of workloads. However, Brown himself explicitly mentions the difficulty of developing a feedback-based tuner that controls more than one knob, amid he is forced to conduct extensive experimentation to devise the heuristics that his tuner uses to adjust two knobs its concert.
Although feedback-based methods can, in theory, avoid the need for training and model building required by model-based methods, the examples presented above demonstrate that experimentation and the development of heuristics are often required to construct an effective feedback-based tuner. Even the examples that do not mention the need for this type of preliminary work would need some means of determining the threshold values that guide the tuner's knob adjustments.
In regards to prediction models, Brewer uses regression models to tune library subroutines. He employs linear regression but allows the independent variables to be nonlinear (e.g., an independent variable can represent time product of two or more of the parameters of the subroutine being optimized). Although this approach works well for tuning subroutines, it is unclear whether it would be possible to produce accurate regression-based performance models of large-scale software systems.
Matthews et al. use a model-based approach to tune a modified version of the log-structured file system (LFS). For example, they enable LFS to dynamically choose the better of two methods for performing garbage collection on the log that the system maintains on disk. Their models consist of simple formulas for estimating the cost or cost-benefit ratio of the possible knob settings; they are based on an understanding of the operations performed by the system and their associated costs. The models only parameters are measurements of the costs of various operations on a particular disk. The authors assess the effectiveness of their approach through simulations of both LFS and the disk on which it resides. It is unclear how well such simple models would work on an actual system, or whether it would even be possible to predict the performance of more complex systems using such models.
In a relational database system, indices and materialized views are supplemental data structures that can be created in an attempt to speed up frequently occurring database queries. The AutoAdmin project has developed model-based techniques for automating the selection of which indices and materialized views to create. The authors use the cost estimates of time database system's query optimizer as time model, and they develop novel methods for selecting which indices and materialized views to consider and for efficiently searching through the space of possible combinations of indices and materialized views. The internal models of time query optimizer are not discussed, and thus it would he difficult to transfer their approach to an arbitrary software system.
In the Odyssey platform for remote computing, applications adapt to changes in resource availability and user goals by varying the fidelity with which they operate (e.g., the frame rate used by a streaming video application). Narayanan et al. augment Odyssey with a system that uses models to predict an applications resource usage as a function of the relevant input parameters and fidelity metrics, and to thereby recommend appropriate fidelity levels for a given operation. To avoid annoying the user, the initial training data is collected during a special offline mode in which a given operation is repeatedly run using randomly chosen fidelities and inputs, and the parameters of the models are refined as the system runs. For their initial prototype, Narayanan et al. employ linear regression to derive the models, and they use linear gradient descent to update the models coefficients over time. To determine the appropriate fidelities for a given set of inputs, the tuning system employs a gradient-descent solver.
Menasc et al. use a tuner based on queueing network models to optimize time quality of service (QoS) of an e-commerce site. When their system detects that a QoS guarantee has been violated, it employs a hill-climbing search guided by the models predictions to find the knob settings that yield the locally maximal QoS. The authors present results showing that their tuner, which adjusts four knobs, is able to maintain reasonable QoS values in the face of increasing load. However, although queueing network models work well in this domain in which the knobs being tuned are directly connected to queues of requests waiting to be processed by a Web server and an application server it is unclear whether they could form the basis of a general software tuning methodology.
Vuduc et al., after discussing how empirical comparisons can be used to determine the optimal implementation of a library subroutine for a given platform, note that the best implementation may depend on the input parameters. Therefore, they propose taking a set of several good implementations (possibly found using empirical comparisons) and using models derived from training data to determine which of these implementations is best for a given set of inputs. They experimentally compare the ability of three types of models including the regression models proposed by Brewer amid a statistical classification algorithm known as time support vector method to choose between three candidate algorithms for matrix multiplication. The latter method has the best performance of the three, but it is unclear how well it would scale to tuning problems with more than one knob or, more generally, to problems with larger numbers of possible knob settings.